Technical Field
Methods and example implementations described herein are generally directed to hardware hash tables, and more specifically, to a hash table applicable to CPU caches and cache coherence directories within a cache coherent system.
Related Art
In related art computer systems, instructions and data were stored and fetched from a main storage by a memory subsystem control for execution or use by a central processor unit, or possibly by some special function unit, such as a floating-point processor. In a few systems, some instructions and data may be retained after their use in a cache memory, which can be accessed more quickly than the main storage. As a result, such instructions and data can be reused later in the execution of the same program. This related art scheme improves the execution performance of the computer system by reducing the time taken to fetch the instructions and data for processing by the central processing unit.
In related art computer systems that have cache memories, the number of cycles required to retrieve an instruction or a data item depends on whether the data item is already in the cache or not, and on how many instructions are required to address or retrieve the data item. If the data item is not in the cache (e.g., a “cache miss”), the instruction or data item must be fetched from main memory, which consumes some number of instruction cycles. If the data item is in the cache, some instruction cycles will also be consumed, although the consumed instruction cycles will be fewer than in the case of a cache miss. Nevertheless, any improvement that can be made in the processing of cached data and instructions is useful. In certain circumstances, the improvement may make a considerable difference to the processing performance of the system.
FIG. 1(a) and FIG. 1(b) illustrate cache memory architectures 100 and 110 respectively, showing placement of cache memory in the hardware layout. As is illustrated, cache memory 104 is positioned between CPU 102 and main memory 106. Data block access from the cache 104 is much faster when compared with access of the same data block from the main memory 106. Similarly, FIG. 1(b) illustrates multiple caches 114, 116, and 118 configured between the CPU 112 and main memory 120.
Most related art caching techniques have a fundamental tradeoff between cache latency and hit rate, wherein larger caches have better hit rates but longer latency. To address this tradeoff, many computers use multiple levels of cache, with small fast caches backed up by larger, slower caches. Multi-level caches generally operate by checking the smallest level 1 (L1) cache 114 first. If a hit occurs in L1, the processor proceeds at high speed. If the smaller cache misses, the next larger cache 116 (L2) is checked, and so on to L3 caches such as 118, before external/main memory 120 is checked.
FIG. 2(a) illustrates structural layout of cache memory 200. As is illustrated, the cache memory 200 comprises multiple blocks, each having a length of K words. Each block line is also associated with a tag that identifies the block being stored. Tag is usually the upper portion of the memory address. As illustrated, the cache memory 200 comprises C blocks, which is much lesser than the number of blocks, say M, of the main memory. FIG. 2(b) illustrates architectural layout of interactions 250 between cache memory 254, processor 252, and system bus 260 through address buffer 256 and data buffer 258. As represented, processor 252 sends address level instructions to the cache to identify the location of data block that is to be fetched along with issuing data requests to the cache 254. Address information paths are provided between the CPU 252, cache 254, and address buffer 256, whereas data information paths are provided between CPU 252, cache 254, and data buffer 258. The cache 254, address buffer 256, and the data buffer 258 all interact with the system bus 260 to receive data blocks and interact with the main memory (not shown).
Typically, a cache is divided into a number of sets of lines, wherein each set comprises a fixed number of lines. A data block from main memory can be configured to map to any line in a given set determined by the respective block address. For instance, in case there are “m” number of lines in the cache, “v” number of sets, and “k” number of lines per set, the value of k would be k=m/v. In such a case, a main memory block number “j” can be placed in a set “i” based on the equation, i=j modulo v.
Improvements in cache memory performance have been sought using various methods of linking and associating groups of cache lines so as to form a policy that is configured to decide where in the cache a copy of a particular entry of main memory will go. If the policy is free to choose any entry in the cache to hold the copy, the cache is called “fully associative”. At the other extreme, if each entry in main memory can go in just one place in the cache, the cache is “direct mapped”. Many caches implement a compromise in which each entry in main memory can go to any one of N places in the cache, and are described as “N-way set associative”. For instance, in a 2-way set associative, any particular location in main memory can be cached in either of 2 locations in a data cache. Similarly, in a 4-way set associative, any particular location in main memory can be cached in any of the four locations in a data cache. Multiple algorithms can be used for determining the location in which the data block can be stored.
Indexing in a cache design refers to a method of storing each address in a subset of the cache structure. A common related art mechanism involves using low-order address bits to determine the entry, or the set of entries, that a data block can be stored in. By restricting addresses to a very small set of entries, there is a possibility that the most useful data (usually the most recently used data) may all map to the same set of entries. Such a mapping would limit the effectiveness of the cache by utilizing only a subset of the entire structure. For indexed caches to work effectively, the addresses needed by a program at any particular time need to be spread across all of the sets of the cache. Addresses spread across the cache allow full use of the lines in the cache. Most programs naturally have a good distribution of addresses to sets, which is one reason caches work well in general.
A cache miss refers to a failed attempt to read or write a piece of data in the cache, which results in a main memory access with much longer latency. A cache write miss to a data cache generally causes the least delay, because the write can be queued and there are few limitations on the execution of subsequent instructions. The processor can continue until the queue is full.
Lowering the cache miss rate is a major area of focus. Therefore, a great deal of analysis has been done on cache behavior in an attempt to find the best combination of size, associativity, block size, and so on. There can be multiple kinds of cache misses, which can impact the cache and processing performance in different ways. For instance, compulsory misses are those misses that are caused by the first reference to a location in memory. Cache size and associativity make no difference to the number of compulsory misses but prefetching data can help here, as can larger cache block sizes. Capacity misses are those misses that occur regardless of associativity or block size of the cache memory, solely due to the finite size of the cache. Conflict misses, on the other hand, are misses that could have been avoided had the cache not evicted an entry earlier. Conflict misses can be further broken down into mapping misses, that are unavoidable given a particular amount of associativity, and replacement misses, which are due to the particular victim choice of the policy (e.g., such as a replacement policy).
While the natural address distribution in programs is generally acceptable, cache performance is often limited by inadequate distribution. Some critical code sequences may concentrate activity in a particular set, which results in new lines replacing other lines that are still useful. If the program tries to access the replaced lines, the program will result in a cache miss and performance will be reduced while the processor waits for the cache to be refilled. As explained above, these caches misses are referred to as conflict misses. The cache itself may be large enough to store all of the useful lines, but the limitations due to indexing force useful lines out of the cache even though there are less useful lines elsewhere in the cache.
There are a few methods of reducing the problem of conflict misses. One way is to allow each address to go to multiple locations (set-associative). This method allows hardware to choose among several possible lines in the cache to evict. Performance can be improved by carefully selecting which line to replace, making sure the least useful address is replaced. A different approach to reducing conflict misses is to improve upon the natural distribution of addresses across sets. Using low-order bits provides a good distribution, but some patterns may exist that lead to less distribution and more conflicts. These patterns can happen because programs are written by people and compiled in a non-random manner.
To improve distribution, an index hash can be used. Hashing involves manipulating the address in such a way that any natural pattern is less likely. Hashing can be implemented by means of a hash table that uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found. As the hash functions typically introduce randomness in the placement of the data blocks based on indexes calculated such as by XOR-ing high-order bits with low-order bits, usage of hash tables is one way to “randomize” the placement of data blocks, which can lead to a more even distribution.
To make room to store additional blocks (e.g., data or instructions copied from the storage device or the memory device), each cache may have a replacement policy that enables the cache to determine when to evict (e.g., remove) particular blocks from the cache. Multiple replacement policies exist for deciding which position to load the new data block to. A random replacement policy, for instance, places the new data block in any set/block of the cache memory, but increases the probability of the miss rate, as high priority data blocks may be made to leave the cache in such a process. Other policies can include first in, first out (FIFO), which makes the oldest block exit from the cache. Least recently used (LRU) is yet another technique used for block replacement.
Shared-memory multiprocessors have been applied quite considerably in high performance computing. They continue to become more relevant in the age of large multicore systems on chip (SoC). Address space is typically shared among multiprocessors so that they can communicate with each other through that single address space. When data is shared by multiple agents, a cache line can be present in more than one cache. When multiple copies exist, coherency may become an issue. Data should be consistent across all caches. The same cache block in multiple caches would result in a system with caches because of sharing of data. This problem does not affect the read process. However, for writes when one processor writes to one location, this change has to be updated to all caches. Most cache coherency protocols have a shared state in which data can be shared between any number of system components (e.g., processors). The shared (S) state arises when a system component requests a read-only copy of the data and the data was already in an Exclusive (E) state in another system component.
The requesting system component and the system component that had a copy of the data each mark the data in shared state. When data is in the shared state, that data can be freely copied by the system components requesting a read-only copy of the data. In a system, cache coherency protocols can either permit a system component to provide the shared data to a requesting system component or the data can be retrieved from the higher memory level directly.
In directory-based cache coherency system, the cache line addresses being shared by agents in the system are tracked in a directory that maintains the coherence information between agent caches. The directory acts as a filter through which the processor must ask permission to load a cache line from the primary memory to its cache. When a cache line is modified, the directory either updates or invalidates the other caches with that entry. A cache coherence protocol uses data structures and messaging to track and co-ordinate the locations of all cached copies of every block of shared data. These cache coherency maintenance data structures can be centralized or distributed and are called directories. For each block of data there is a directory entry that contains a number of pointers. The purpose of the pointers is to mention the system agent where block copies are located and, as a result, keep track of the cached copies of the data block.
When the number of sharer agents in the system is large, maintaining a bit vector for the sharers is more efficient than binary pointers for each sharing agent. Each directory entry also contains a write-permission bit to specify whether a unique cache has a permission or not to write the associated block of data. In implementation, a cache miss results in communication between the node where the cache miss occurs and the directory so that the information in the affected caches is updated. A coherency protocol is a set of mechanisms to maintain coherence between the caches in the system. It defines the states of the cache lines in the system, conditions and transition between the states and operations and communications performed during coherent read and write requests. MSI is an example of a coherence protocol employed to maintain coherence in a multi-processor system. The letters M (modified), S (shared) and I (Invalid) in the protocol name identify the possible states in which a cache line can be as specified by the protocol.
Each directory entry typically contains a tag corresponding to the address of a given memory block, identifying information for locating all processors that are caching the block, and a status field indicating whether the cached copies are valid. The directory information of a node is used to evaluate read and write requests pertaining to the memory blocks of the node, and to send out coherency messages to all caches that maintain copies. When a processor in the system updates a shared memory block, the directory having jurisdiction over the memory block is consulted to determine which caches hold copies of the block. Before the write operation can proceed, invalidation messages are sent to the identified caches and invalidation acknowledgements must be returned to verify that all cached copies have been invalidated. In similar fashion, when a processor requests read access to a shared memory block, the directory having jurisdiction over the block is consulted to identify the location and status of all cached copies. Based on the information in the directory, the requested block can be provided to the requestor from one of the caches holding a valid copy, or from the main memory of the node that stores the block.
An efficient data structure is typically needed to implement directory tables where coherent cache lines addresses, their sharers, and states are tracked. Architecture of such a directory table should have an implication on the total amount of memory needed for tracking all coherent cache line addresses in the system, utilization of this memory, and performance of the system.
Snooping is a process where the individual caches, monitor address lines for access to memory locations that they have cached instead of a centralized directory-like structure handling the monitoring. When a write operation is observed to a location that a cache has a copy of, the cache controller invalidates its own copy of the snooped memory location. In the snooping solution, a snoopy bus is incorporated to send all requests for data to all processors, wherein the processors snoop to see if they have a copy and respond accordingly. This mechanism therefore involves a broadcast, since caching information is stored in the processors. A multiple snoop filter reduces the snooping traffic by maintaining a plurality of entries, each representing a cache line that may be owned by one or more nodes. When replacement of one of the entries is required, the snoop filter selects for replacement the entry representing the cache line or lines owned by the fewest nodes, as determined from a presence vector in each of the entries. A temporal or other type of algorithm is used to refine the selection if more than one cache line is owned by the fewest number of nodes.
A class of dictionary data structures called Hash tables are associative structures used to store and access [Key, Value] pairs. The defining characteristic of hash table lookup is that for a majority of access requests, a key's value is located in a linear table at an address that is determined directly by applying a function, i.e., the hash function, to the key. Because the location for storing the value is known from the key (except in those cases where there is a hash function collision), a hash table lookup can be performed on average in constant time. Hashing mechanisms play an important role in many computer systems.
One such example of a related art hashing mechanism 300 is depicted in FIG. 3. The hashing mechanism 300 comprises a key 302, a hash function 304, a hash index 306, and a hash table 308. The hash table 308 contains a number of hash buckets 310-330, and each hash bucket contains data, such as a record, with one of the fields of the record acting as the key 302. To access the hash table 308, the key 302 is input into a hash function 304, which yields an index 306 (or hash address) that refers to a specific hash bucket (e.g., 314). Within the hash bucket 314 is the data that matches the key.
Hash tables are useful because they provide direct access to data by mapping a large range of key values into a smaller range of indexes. In this manner, for example, if a key of eight digits were utilized having a range of key values from 0 to 99,999,999 and if less than ten values are ever used, a hashing mechanism can be used to hash the key into an index of one digit to refer to a hash table containing ten buckets. Therefore, instead of using a hash table having one-hundred-million hash buckets where only a very limited number of the buckets are ever used, a hash table of only ten buckets can be used to more efficiently use system resources, but still provide direct access to the data. The function “h” 304 maps each key value onto exactly one index, and therefore, whenever the same key value is used more than once, the same index 306 into the hash table 308 is generated. Sometimes, however, when attempting to store data in the hash table 308, more than one key value will hash to the same index 306. In this situation, a “collision” has occurred.
When a collision occurs, the data must be stored in the hash bucket indicated by the index and therefore more than one record will be stored in this hash bucket. Hash bucket 318 depicts the state of a hash bucket after a collision has occurred and more than one record is stored in the hash bucket. In hash bucket 318, one record of data “Data 3” is linked to a second record of data “Data 4.” As more collisions occur, the hash buckets become more populated and thus the benefits of a hash table start to diminish because each record within the hash bucket is no longer directly accessible. Instead, after hashing the key value into an index, the index refers to a hash bucket that contains a number of records linked together and the hash bucket must then be searched to determine the correct record, which is costly in terms of processing time. Therefore, related art hashing systems are designed to avoid collisions.
Any hash set algorithm must deal with collisions. Collisions are when two distinct items hash to the same table entry. Open addressing algorithms typically resolve collisions by applying alternative hash functions to test alternative table elements. Closed addressing algorithms place colliding items in the same bucket, until that bucket becomes too full. In both types of algorithms, it is sometimes necessary to resize the table. In open addressing algorithms, the table may become too full to find alternative table entries, and in closed addressing algorithms, buckets may become too large to search efficiently. Open addressing schemes have the potential performance advantage of involving one level less of indirection in accessing an item in the table, since the item is placed directly in an array, not in a linked list implementing a bucket.
One important statistic for a hash table is called the load factor, which is simply the number of entries divided by the number of buckets, that is, α=n/k, where α is the load factor, n is the number of entries, and k is the number of buckets. If the load factor α is kept reasonable, the hash table should perform well, provided the hashing is good. If the load factor α grows too large, the hash table will become slow, or it may fail to work (depending on the method used). For a fixed number of buckets, the time for a lookup grows with the number of entries and so does not achieve the desired constant time. If the set implementation used for the buckets has linear performance, then O (1+α) time may be required to do add, remove, and member. To make hash tables work well, it is necessary to ensure that the load factor α does not exceed some constant αmax, so all operations are O(1) on average.
Cuckoo hashing is a related art multiple-choice hashing scheme that gives better space utilization by moving elements around as needed. This technique was originally presented by Pagh and Rodler in Cuckoo Hashing, Proceedings of the 9th European Symposium on Algorithms (2001). Cuckoo hashing employs two hash functions and two respective hash tables (T1 and T2), which may be considered to be two portions or subtables of a single cuckoo hash table. Each entry is stored in a bucket of T1 or a bucket of T2, but never in both.
FIG. 4 is a diagram of cuckoo hash tables arranged according to related art principles. Here, the table T1 is identified by reference number 400 and the table T2 is identified by reference number 450. As explained, a given key will be hashed by the first hash function to determine its bucket in table T1 and that same key will be hashed by the second hash function to determine its bucket in table T2. In other words, using the same nomenclature, T1[h1(x)]=x and T2[h2(x)]=x, where h1 is the first hash function, h2 is the second hash function, and x is the key.
In practice, therefore, a given key is hashed using the two different hash functions to obtain two possible cuckoo hash table locations or buckets (alternatively, a single hash function with multiple results can be used). Then, those buckets can be searched for the key. If the key is found in one of the two buckets, then data stored with that key can be accessed, retrieved, processed, etc. As an example, FIG. 4 illustrates that Key A can be potentially stored in its respective bucket 402 in table 400 or in its respective bucket 458 in table 450. The arrow between bucket 402 and bucket 458 indicates potential movement or pushing of Key A between bucket 402 and bucket 458. As depicted in FIG. 4, Key B has its potential locations in table 400 and table 450, Key C has its potential locations in table 400 and table 450, and Key D has its potential locations in table 400 and table 450. In practice, table 400 and/or table 450 can include a number of empty buckets such as 406 to accommodate the insertion of new keys (and corresponding data) and to accommodate pushing of existing keys between table 400 and table 450.
A hash function may generate the same hash value (i.e., a locator or identifier for a given bucket) for two or more different input values. In other words, given a first key x1 and a second key x2, h1(x1) might equal h1(x2). In a cuckoo hash table, collisions are handled by moving entries from one table to another. With this in mind, FIG. 5(a) and FIG. 5(b) are diagrams (used for purposes of this simplified example) that illustrate pushing of keys in cuckoo hash tables. FIG. 5(a) depicts the status of the first table 500-1 and the second table 500-2 at a time when an entry (Entry X, which includes Key X and corresponding data) is to be inserted. The shaded areas represent occupied or unavailable buckets in the table. As explained above, the two hash functions indicate that Entry X can be inserted into the bucket 504 of table 500-1 or into the bucket 510 of table 500-2 (but not both). This example represents an attempt to initially insert Entry X into bucket 504. The arrows in FIG. 5(a) and FIG. 5(b) indicate the manner in which the given entry can be pushed from table 500-1 to table 500-2, or vice versa. Thus, referring to FIG. 5(a), although Entry Y is contained in bucket 504, it may alternatively be contained in the bucket 508 of table 500-2. Similarly, although Entry Z is presently contained in bucket 508, it may be pushed into the bucket 502 of table 500-1. It is to be noted that bucket 508 may contain either Entry Y or Entry Z, meaning that the hash function h2(x) will generate the same value (corresponding to bucket 508) using either Entry Y or Entry Z as an input value. Moreover, Entry V can be moved from its current location (the bucket 506 of table 500-2) to its alternative location, namely, bucket 502 of table 500-1.
FIG. 5(b) depicts the status of the first table 500-1 and the second table 500-2 after insertion of Entry X and pushing of Entry Y and Entry Z. As shown, Entry X is now contained in bucket 554. Entry X displaced Entry Y, which has been pushed to bucket 558. In turn, Entry Y displaced Entry Z, which has been pushed to bucket 552. The insertion of Entry X was possible because bucket 552 of table 500-1 was empty prior to the insertion operation (see FIG. 5(a)). If the cuckoo hash tables are appropriately sized and managed, then enough empty buckets can be maintained to ensure that insertion and other operations do not fail.
In implementations involving a cuckoo directory, having multiple cuckoo ways allows addresses greater probability of finding an unused entry. The directory always has the possibility of empty spots, whereas a cache is just filled. The directory can be sized as needed.
As described above, conflicting entries may occur in a cuckoo directory. For example, suppose one address A wants to hit two different entries in the directory that are both full B and C. An address has to be selected. In related art implementations, algorithms such as least recently used (LRU) can be employed to select an address. One of the entries needs to be evicted, and thus one of the directory entries from B and C are evicted, and replaced by A. When this eviction occurs, the cache must send an invalidation instruction or flush to coherent system instruction to write back dirty data and write back copies as the address is being evicted. However, this situation should be avoided because performance may degrade from the invalidation or flush instruction.